Міністерство освіти і науки, молоді та спорту України Національний університет „Львівська політехніка” Кафедра СКС Звіт з лабораторної роботи №1 з дисципліни: “ Дискретна математика ” на тему: “Операції над множинами” ТЕОРЕТИЧНА ЧАСТИНА 1.1. Множини Множини є основними об’єктами вивчення у дискретній математиці. Множина - це невпорядкована сукупність об’єктів, які називають елементами множини. Елементами можна вважати довільні об’єкти, які можуть бути названі або означені за допомогою правила, що задає належність до множини. Як правило, множини позначають великими буквами. Прикладе множин: множина всіх трамвайних зупинок міста Львова; множина символів клавіатури ЕОМ; множина зарезервованих слів мови Паскаль; А = {х ǀ х - ціле число і 7 < х < 13}; N = {1, 2, 5, 9, 14, 13} - множина задана перечисленням її елементів. Для будь-якого елемента можна встановити, чи належить він множині
. Запис
означає приналежність елемента
до множини
, а символ «
» - це знак приналежності деякого елемента до множини
. Запис
означає, що елемент
не належить до множини
. 1. Операції над множинами Розглянемо дві множини А і В та введемо низку операцій над ними. Для графічної ілюстрації використовують діаграми (кола) Ейлера. Для зображення множини на площині креслять замкнену лінію із заштрихованою внутрішньою областю (найчастіше – це коло, звідси й назва відповідного інструмента, що широко застосовується в теорії множин). 1.1. Об’єднання А і В – множина, що складається з усіх елементів множини А, всіх елементів множини В і не містить ніяких інших елементів (рис. 1), тобто А ( В = {x | x ( А або x ( В}.
Рис. 1 1.2. Перетин А і В – множина, що складається з тих і тільки з тих елементів, які належать одночасно множині А та множині В (рис. 2), тобто А ( В = {x | x ( А і x ( В}.
Рис. 2 1.3. Різниця А і В (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині А й не належать множині В (рис. 3), тобто А \ В = {x | x ( А і x ( В}.
Рис. 3 1.4. Диз’юнктивна сума А і В (симетрична різниця) – множина, що складається усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А, та яка не містить ніяких інших елементів (рис. 4), тобто А ( В = {x | (x ( А і x ( В) або (x ( В і x ( А)}.
Рис. 4 1.5. Доповнення множини. Звичайно, вже в означенні конкретної множини явно або неявно обмежується сукупність об’єктів, що є допустимими (слони – серед тварин, натуральні числа – серед цілих або дійсних залежно від контексту). Зручно сукупність допустимих об’єктів зафіксувати явно та вважати, що множини, які розглядаються, складаються з елементів цієї сукупності. Її називають основною множиною (універсумом) і позначають U. Універсум U арифметики – числа, універсум U зоології – тварини і т.д. Будь-яку множину розглядатимемо у зв’язку з універсумом, який на діаграмах Ейлера асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини (рис. 5).
Рис. 5 Доповнення множини А – це множина, що містить усі елементи універсуму, за винятком елементів А (рис. 6), тобто
.
Рис.6 1.8. Множина А називається підмножиною множини В, якщо кожен елемент А є елементом В. Для позначення цього факту вводиться знак ( - символ строгого включення (або ( - символ нестрогого включення) (рис. 7). Якщо необхідно підкреслити, що множина В містить також інші елементи, крім елементів множини А, то використовують символ строгого включення А ( В. Дві множини рівні, якщо вони складаються з одних і тих самих елементів. Справджується таке: А = В тоді і тільки тоді, коли А ( В і В ( А.
Рис. 7 1.6. Декартовим (прямим) добутком множин A і B (записується A(B) називається множина всіх пар (a,b), в яких перша компонента належить множині A (a(A), а друга - множині B (b(B). Тобто A(B = {(a,b) | a(A і b(B } Декартовий добуток природно узагальнюється на випадок довільної скінче...